package 二分;


/**
 * leetcode 宫水三叶 的  提供的 相关的  二分 题
或者 卡尔 carl    相关的    二分 题目 
 *https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/solution/by-ac_oier-to07/ 
 * 
 * 
 * 
 * 
 *
 * 
 * 
 * 
 * 
 * 认识二分法 :
 * 1. 在一个数组中 查找某个数 是否存在
 * 2、在一个有序数组中 找 》= 某个数最左位置 的  下标 
 * 3，同上 《= 某个数  最 右侧 的    下 标
 * 
 *  
 * 4.局部  最小值问题  有点  类似于 单调性的 问题  
 * 
 * 
 * 
 * 
 * 
 * 
 *  二分法 从来 不都是  有序 才能使用的   就比如上面的       局部最小问题    就不是要求数组严格有序
 */

import org.junit.Test;

/**
 * 
 * 二分的 前提 一定 是  要求  有序 嘛  （这得 分 什么 类型得 二分 了）
 * 
 * 
 * 对二分 
 * 
 * 原始 数组 的 元素 又分为 两种 情况 ① ：数组中 没有重复元 元素 
 *  ②： 数组中 有 重复元素  （这种 因该是 最常见的情况 ） 
 *  	有重复元素的 又分为 ①：找到 最左边的    ②：找到 最右边的  
 * 
 * 
 *  ①：普通 while  循环的的  二分  
 *  ②： 递归 进行二分 
 * 
 * 
 * @author I adore you
 *
 */
public class Note {
	
	/**
	 * 下面 实现 >=  或者  只是 (大于) > 某个数   value 的 最左边的 的数的 下标
	 * >= 或者 (大于)  > value 只会让你求 最左边的 数的 下标 
	 * 为啥  
	 * 因为 >= 或者 (大于)  > 只会让你 求最左侧的 值 下标 
	 * 因为 画个 图 在纸上 理解一下就明白 了  
	 * >=  和  > 是有点 区别 的 
	 * 这个 问题 要想 十分 通透的  理解 必须 得 去 画图 去  慢慢的 理解 
	 * 有点  小 绕
	 */
	/**
	 * 对于 getLeftIndex 和 getRightIndex 这两个函数
	 * 如果 nums 数组中 不存在 指定的 值  target
	 * nums [] = {1,2,3,6,8,12,12,12,12,14,15,19,22,44,46};
	 * 如上例子：
	 * 查找  target = 13 nums数组中 就没有这个元素 
	 * 那么对于 getLeftIndex 来说会 返回  >= 13 的 最左边的元素 也就是  14 (如果有多个14 会返回最左边的 14)的下标
	 * 同理对 于 getRightIndex 来说 会返回  <= 13 的最右边的元素的  12(有多个 12 会返回 最右边的 12 )的下标  
	 */
	
	
	public static int getLeftIndex(int nums[],int value) {
		/**
		 * 用这个 index 记录着 并更新 这个  满足条件的 最左侧的下标
		 * 可以 省去 
		 * 但是 没必要 
		 * 就算 多用  这一个  int 的变量 又不会 死 干嘛 写的 那么  去 扣 coding 的 简洁
		 */
		int index = -1;
		int l = 0 ;
		int r = nums.length - 1;
		int mid = 0;
		while(l <= r) {
			mid = l + ((r - l )>>1);
			/**
			 * 这里 做个 解释   
			 * int arr []= {5,7,7,8,8,10};
			 * value  = 7
			 * 对于上面 的   数组 来说 
			 * 条件是 nums[mid] >= value 时候返回的 是   index 是 1
			 * 而条件 是   nums[mid] > value 的时候 返回的 结果 是 index 是 3
			 * 这就不需要 我多解释了 吧 
			 */
			if(nums[mid] >= value) {
				index = mid;
				r = mid -1;
			}
			else {
				l  = mid + 1;
			}
		}
		return index;
	}
	
	/**
	 * 下面 实现 <= 或者  只是 (小于) < 某个数   value 的 最右 边的 的数的 下标
	 * < = 或者 (小于 )  < value 只会让你求 最 右 边的 数的 下标 
	 * 为啥  
	 * 因为 <=  或者 (小于)  < 只会让你 求 最  右 侧的 值 下标 
	 * 因为 画个 图 在纸上 理解一下就明白 了  
	 * <=  和  < 是有点 区别 的 
	 * 这个 问题 要想 十分 通透的  理解 必须 得 去 画图 去  慢慢的 理解 
	 * 有点  小 绕
	 */
	
	public static int getRightIndex(int nums[],int value) {
		int l = 0;
		int r = nums.length - 1;
		int index = -1;
		int mid = 0;
		while(l <= r) {
			mid = l + r >> 1;
		/**
		 * 这里 做个 解释   
		 * int arr []= {5,7,7,8,8,10};
		 * value  = 7
		 * 对于上面 的   数组 来说 
		 * 条件是 nums[mid] <= value 时候返回的 是   index 是 1
		 * 而条件 是   nums[mid] < value 的时候 返回的 结果 是 index 是 0
		 * 这就不需要 我多解释了 吧 
		 */
			if(nums[mid] <= value) {
				index = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1 ;
			}
		}
		return index;
	}
	
	
	
	
	
	
	
	
		/**
		 * 写一个 比较 经典的 递归 二分 
		 * 
		 * 
		 * 这里 果然 要 注意 一个点 就是 
		 * l 与   r 布尔 关系  
		 * 只是二分 查找的 话    要写 成  l <= r 
		 * 为啥  因为 写成  l < r 的 情况  在 数组 的 长度 为 二 的 时候 会出问题的  
		 *在 纸上分析 一下 就明白这个 过程 
		 *主要 是 mid 和 mid -1
		 *还有 mid + 1 引起的 边界 判断问题
		 *
		 */
	public static int recursionBinarySearch(int nums[],int l,int r,int aim) {
		if(l <=r) {
			
			int mid = l + ((r - l) >> 1);
			if( aim < nums[mid]) {
				return recursionBinarySearch(nums,l,mid,aim);
			}
			else if(aim > nums[mid]) {
				return recursionBinarySearch(nums,mid + 1,r,aim);
			}
			else if(aim == nums[mid]) {
				return mid;
			}
		}
		return -1;
		
	}
	/**
	 *再来个 while 循环的 二分  
	 * 
	 * 这个 时 只能  解决 能找到 得问题 但是
	 * 如果 有多个 重复 目标 值 那        这种 二分 可能 找到得 索引值 并非 时 你想 要 的 下标  
	 */
	public static int plainBinarySearch(int nums[],int l,int r,int aim) {
		int mid = 0;
		while(l <= r) {
			mid = (l+r)>>1;
			if( aim < nums[mid]) {
				r = mid -1;
			}
			else if( aim > nums[mid]) {
				l = mid + 1;
			}
			else if(aim == nums[mid]) {
				return mid;
			}
		
		}
		return -1;
	}
/**
 * 	下面的 代码 是错的 死循环
 */
	
	public static int plainBinarySearchUpdate(int nums[],int l,int r,int aim) {
		int mid = 0;
		while(l <= r) {
			mid = (l+r)>>1;
			if( aim < nums[mid]) {
				r = mid -1;
			}
			else if( aim > nums[mid]) {
				l = mid + 1;
			}
			else if(aim == nums[mid]) {
			    /**
			     * 从找到的 位置 开始  向前 （出现最左边  或者成为 第一次出现 aim 的位置  ）  
			     * 或者   向后 （最后 一次 出现 aim 的 位置 ） 遍历 
			     */
	
				/**
				 * 找   最后一次   出现的 位置 
				 */
				for(int i = mid + 1; i < nums.length ;i++) {
					if(aim < nums[i]) {
//						  这里   是 i -1   注意 一下 
						return i - 1;
					}
				}
//				return mid;
				/**
				 * 找到 第一次 aim  出现的 位置  
				 */
//				for(int i = mid -1;i >= l;i--) {
//					if(aim > nums[i]) {
//						return i - 1;
//					}
//				}
				
				
				
			}
		
		}
		return -1;
	}




		// ===============  更新 2023/2/6   掌握 了 板子 再重新 写这个题======================
	/*
	 通过 一个 index 变量, 可以处理
	 如果, 要找的 值 不存在 的情况
	 返回 -1 的这种 情况
	 index = -1
	 如果, 不能 完全 保证, 要找的 x 一定在 [l , r] 闭区间内的话,
	 不要 吝啬 这个 一个 变量index
	 */
	@Test
	public void testLeft(){
		/*
		有序 集合!
		找出  >= x 最左边得 值
		或者  > x 得最左边得 值
		> x 最左边得 值 ,等价于 >= x + 1 最左边 的 值
		 */
		int arr []= {5,7,7,8,8,10};
		int target = 8;
		int l = 0,r = arr.length - 1;
		int index = -1;
		while(l < r){
			int mid = l + r >> 1;
			if(arr[mid] < target){
				l = mid + 1;
			}
			else{
				index = mid;
				r = mid;
			}
		}
		System.out.println(index);
	}
	@Test
	public void tes2(){
		/*
		有序 集合!
		找出  <= x 最右边得 值
		或者  < x 得最右边得 值
		< x 最左边得 值 ,等价于 <= x -  1 最右边 的 值
		 */
		int arr []= {5,7,7,8,8,10};
		int target = 1;
		int l = 0,r = arr.length - 1;
		int index = -1;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(arr[mid] > target){
				r = mid - 1;
			}
			else{
				index = mid;
				l = mid;
			}
		}
		System.out.println(index);
	}
/*
  没办法找到 确定的值
  就是  说 , 找不到 的 话,不会返回 - 1
  所以 我们要求 答案 ,必须 在 给定的 闭区间的 范围 内 , 否则会有问题!
 */
	@Test
	public void test3(){
		int arr []= {1,2,3,5,7,20};
		int target = 6;
		int l = 0, r = arr.length - 1;
		while(l < r){
			int mid = l + r >> 1;
			if(arr[mid] < target){
				l = mid + 1;
			}
			else{
				r = mid;
			}
		}
		System.out.println(l);
	}
}
